/**
 *  Filename: PairedAttribute.java
 *  Purpose:  Calculates a Boyce-Codd normal form decomposition from an input relation
 *            and a set of functional dependencies.
 *  Date:     Nov 1, 2009
 *  Author:   Philippe Gambling
 */

package com.pgamb.Hwk4;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

import com.pgamb.Hwk4.Helpers;

public class PairedAttribute {

	private static Set<Character> R;      // Attributes in relation R
	private static FDSet F = new FDSet(); // The set of functional dependencies
	
	/**
	 *  Name: readFileInput
	 *  Description: Open and read the relational schema's attributes and functional dependencies
	 *               from the input file. 
	 *  Date: 11/02/2009
	 *  @author Philippe Gambling
	 *  @param fname input file name
	 */
	private static void readFileInput(String fname) {
	    try {
			BufferedReader input = new BufferedReader(new FileReader(fname));
	        try {
	        	String line = input.readLine();
	        	int lineNumber = 1;
	        	// Make sure first line contains only letters
	        	if(!line.matches("[a-zA-Z]+")) { 
	        		System.out.println("Error: non-alphabetic character on line "+lineNumber);
	        		System.exit(1);
	        	}
	        	
	        	R = new TreeSet<Character>();
	        	Helpers.String2Set(line,R);
	        	
	        	while (( line = input.readLine()) != null) {
	        		// Read in remaining functional dependency lines 
	        		// and make sure it contains only letters separated by one comma
	        		lineNumber++;
	        		line = line.trim(); // Trim leading or trailing whitespace
	        		if(line.isEmpty()) continue; // Skip empty lines
	        		else
	        			if(!line.matches("[a-zA-Z]+,[a-zA-Z]+")) { 
	        				System.out.println("Error: Improperly formatted functional dependency on line "+lineNumber);
	        				System.exit(1);
	        			}
	        		// Add FD inputs to FDSet
		        	String[] temp = line.split(",");
		        	String lhs = temp[0];
		        	String rhs = temp[1]; 
	        		F.AddFuncDep(lhs,rhs);
	        	}
	        }
	        finally {
	        	input.close();
	        }
	    }
	    catch (IOException ex){
	    	ex.printStackTrace();
	    }
	}
	
	/**
	 *  Name: runPAAlgorithm
	 *  Description: Run the main loop of the paired attribute algorithm 
	 *  Date: 11/02/2009
	 *  @author Philippe Gambling
	 *  @param r the set of attributes in the relational schema
	 *  @param f the set of functional dependencies
	 *  @return a list containing the relational subschema decomposed to BCNF
	 */
	private static List<Set<Character>> runPAAlgorithm(Set<Character> r, FDSet f) {
		// Using a String for the decomposition set to simplify output
		List<Set<Character>> d = new ArrayList<Set<Character>>(); 
		
		boolean bcnf = false;
		Set<Character> z = new TreeSet<Character>(r);
		
		while (!bcnf) {
			bcnf = true;
		    
			// for every ordered pair of attributes A and B in Z
			for(Iterator<Character> itrA = z.iterator(); itrA.hasNext() && bcnf;) {
				Character a = itrA.next();
				Iterator<Character> itrB = z.iterator();
				if(itrB.hasNext()) itrB.next();
				
				Character b = null;
				while(itrB.hasNext() && (b = itrB.next()) != a) {
					// (z - AB)+ with respect to f
					Set<Character> tempSet = new TreeSet<Character>(z);
					tempSet.remove(a);
					tempSet.remove(b);
					Set<Character> closure = f.XClosure(tempSet);
					
					// if A or B is in (z - AB)+ with respect to f then bcnf := false;
					if(closure.contains(a) || closure.contains(b)) { 
						bcnf = false;
						break; // No need to continue checking for bcnf violations
					}
				}
			}
			
		    if (!bcnf) {
		    	Set<Character> y = new TreeSet<Character>();
		    	Character a = decompose(z,f,y);
		    	d.add(y);
		    	z.remove(a);
		    }
		}
		
		// Append remaining attributes in Z to D
		d.add(z);
		
		return d;
	}
	
	/**
	 *  Name: decompose
	 *  Description: Finds a decomposition Y and attribute A such that Y = XA 
	 *               is in BCNF and XA is in F+. 
	 *  Date: 11/02/2009
	 *  @author Philippe Gambling
	 *  @param z the current working set of attributes to decompose
	 *  @param f the set of functional dependencies
	 *  @param y returns a relational subschema
	 *  @return the next attribute to remove from z
	 */	
	private static Character decompose(Set<Character> z, FDSet f, Set<Character> y) {
		boolean flag = true;
		Character a = null;
		y.addAll(z);
		
		
		while (flag) {
			flag = false;
			
			for(Iterator<Character> itrC = y.iterator(); itrC.hasNext() && !flag;) {
				Character c = itrC.next();
				Iterator<Character> itrD = y.iterator();
				if(itrD.hasNext()) itrD.next();
				Character d = null;
				while(itrD.hasNext() && (d = itrD.next()) != c) {
					// (z - CD)+ with respect to f
					Set<Character> tempSet = new TreeSet<Character>(y);
					tempSet.remove(c);
					tempSet.remove(d);
					Set<Character> closure = f.XClosure(tempSet);
					
					// if C is in (Y - CD)+ with respect to F
					Character b = null;
					if(closure.contains(c)) {
						flag = true;
						a = new Character(c);
						b = new Character(d);
					}
					else
						if(closure.contains(d)) { 
							flag = true;
							b = new Character(c);
							a = new Character(d);
						}
					
					if (flag) {
						y.remove(b);
						break; // restart loop
					}
				}
			}
		}
		
		return a;
	}

	/**
	 *  Name: main
	 *  Description: Program entry point
	 *  Date: 11/01/2009
	 *  @author Philippe Gambling
	 *  @param args command-line arguments
	 */
	public static void main(String[] args) {
		if(args.length < 1) {
			System.out.println("Usage: java -jar PairedAttribute.jar <input file>");
			System.exit(1);
		}
		
		// Read input file and check for correct input format		
		readFileInput(args[0]);
		
		// Execute the paired attribute algorithm
		List<Set<Character>> decomposition = runPAAlgorithm(R, F);
		
		// Print final decomposition
		boolean first = true;
		String output = new String();
		for( Set<Character> ri : decomposition ) {
			// Don't add a comma before the first set
			if (!first) output = output + ", ";
			first = false;
			for( Character c : ri ) {
				output = output + c;
			}
		}
		System.out.println(output);
		
		System.exit(0);
	}
}
